package lc.q51_100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
 * 我们将 "rgtae” 称作 "great" 的一个扰乱字符串。
 *
 * 给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
 */
public class Q87 {

    int[][][] memo;
    String s1;
    String s2;
    public boolean isScramble(String s1, String s2) {
        this.s1 = s1;
        this.s2 = s2;
        memo = new int[s1.length()][s2.length()][s2.length() + 1];
        return dfs(0,0, s1.length());
    }

    private boolean dfs(int i1, int i2, int subLength) {
        if (memo[i1][i2][subLength] != 0) {
            return memo[i1][i2][subLength] == 1;
        }
        // 如果两个子串相等,那么返回true
        if (s1.substring(i1, subLength + i1).equals(s2.substring(i2, subLength + i2))) {
            memo[i1][i2][subLength] = 1;
            return true;
        }
        // 如果子串出现的值不同，返回false
        if (!checkIsSimilar(i1, i2, subLength)) {
            memo[i1][i2][subLength] = -1;
            return false;
        }
        for (int i = 1; i < subLength; i++) {
            // 不交换情况，判断两部分子串
            if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, subLength - i)) {
                memo[i1][i2][subLength] = 1;
                return true;
            }
            // 交换情况
            if (dfs(i1, i2 + subLength - i, i) && dfs(i1 + i, i2, subLength - i)) {
                memo[i1][i2][subLength] = 1;
                return true;
            }
        }
        memo[i1][i2][subLength] = -1;
        return false;
    }

    private boolean checkIsSimilar(int i1,int i2, int length) {
        Map<Character, Integer> seq = new HashMap<>();
        for (int i = i1; i < i1 + length; i++) {
            char c = s1.charAt(i);
            seq.put(c, seq.getOrDefault(c, 0) + 1);
        }

        for (int i = i2; i < i2 + length; i++) {
            char c = s2.charAt(i);
            seq.put(c, seq.getOrDefault(c, 0) - 1);
        }
        for (Map.Entry<Character, Integer> characterIntegerEntry : seq.entrySet()) {
            if (characterIntegerEntry.getValue() != 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Q87 q87 = new Q87();
        boolean scramble = q87.isScramble("great", "rgeat");
        System.out.println(scramble);
    }

}
